# s="11106"
# s="226"
s="2101"
# def numDecodings(s):
#     s_len=len(s)
#     print(s_len)
#     if s_len==0:
#         return 0
#     dp=[0 for _ in range(s_len)]
#     if s[0]=='0':
#         #如果第一个元素就是0的话就证明出错了
#         return 0
#     else:
#         dp[0]=1
#     for i in range(1,s_len):
#         if s[i-1]=="1":
#             if s[i]=="0":
#                 if dp[i-1]>1:
#                     dp[i]=dp[i-1]-1
#                 if dp[i-1]==1:
#                     dp[i]=dp[i-1]
#             else:
#                 dp[i]=dp[i-1]+1
#         elif s[i-1]=="2":
#             if s[i]=="1" or s[i]=="2" or s[i]=="3" or s[i]=="4" or s[i]=="5" or s[i]=="6":
#                 dp[i]=dp[i-1]+1
#             elif s[i]=="0":
#                 if dp[i-1]>1:
#                     dp[i]=dp[i-1]-1
#             else:
#                 dp[i]=dp[i-1]
#         else:
#             if s[i]=="0":
#                 #直接报错的情况
#                 return 0
#             #其余情况基本保持不变
#             dp[i]=dp[i-1]
#     print(dp)

def numDecodings(s):
    s_len=len(s)
    if s_len==0:
        return 0
    dp=[0 for _ in range(s_len)]
    if s[0]=="0":
        return 0
    else:
        dp[0]=1
    if s_len>=2:
        if s[0]=="1" or s[0]=="2":
            if s[1]=="0":
                dp[1]=1
            elif s[1]=="1" or s[1]=="2" or s[1]=="3" or s[1]=="4" or s[1]=="5" or s[1]=="6":
                dp[1]=2
            else:
                if s[0]=="1":
                    dp[1]=2
                if s[0]=="2":
                    dp[1]=1
        else:
            if s[1]=="0":
                return 0
            else:
                dp[1]=1
        for i in range(2,s_len):
            if s[i]=="0":
                if s[i-1]=="2" or s[i-1]=="1":
                    dp[i]=dp[i-2]
                    continue
                else:
                    return 0
            if s[i-1]=="1":
                dp[i]=dp[i-1]+dp[i-2]
            if s[i-1]=="2":
                if s[i]=="1" or s[i]=="2" or s[i]=="3" or s[i]=="4" or s[i]=="5" or s[i]=="6":
                    dp[i]=dp[i-1]+dp[i-2]
                else:
                    dp[i]=dp[i-1]
            else:
                dp[i]=dp[i-1]
    print(dp)

numDecodings(s)


